package LeetcodeHot100;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution023 {
    // public ListNode mergeKLists(ListNode[] lists) {
    // PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
    // @Override
    // public int compare(ListNode o1, ListNode o2) {
    // return o1.val - o2.val;
    // }
    // });
    // for (ListNode head : lists) {
    // while (head != null) {
    // pq.offer(head);
    // head = head.next;
    // }
    // }
    // ListNode dummy = new ListNode(0);
    // ListNode result = dummy;
    // while (!pq.isEmpty()) {
    // dummy.next = pq.poll();
    // dummy = dummy.next;
    // }
    // dummy.next = null;
    // return result.next;
    // }
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        // 将每个链表的头节点插入优先队列
        for (ListNode head : lists) {
            if (head != null) // 这里一定要判断不为空
                pq.offer(head);
        }
        ListNode dummy = new ListNode(0);
        ListNode result = dummy;
        // 当链表的头节点出队时，将后续结点加入队列中，直至为空
        while (!pq.isEmpty()) {
            ListNode poll = pq.poll();
            dummy.next = poll;
            dummy = dummy.next;
            if (poll.next != null)
                pq.offer(poll.next);
        }
        // 最后的结点需要指向空结点，防止链表出现环
        dummy.next = null;
        return result.next;
    }
}
